package ermao.queue;

import com.alibaba.fastjson.JSON;
import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * 优先级队列
 *
 * @Description
 * @Author weisl
 * @Date 2024-02-19 09:32:43
 */
@Slf4j
public class PriorityQueue<E> implements Queue<E> {

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    transient Object[] queue;

    private int size = 0;

    public PriorityQueue() {
        queue = new Object[DEFAULT_INITIAL_CAPACITY];
    }

    @Override
    public boolean offer(E e) {
        if (e == null) {
            throw new NullPointerException();
        }

        int i = size;
        // 如果 i=数组长度，需要扩容
        if (i >= queue.length) {
            grow(i + 1);
        }

        size = i + 1;
        if (i == 0) {
            queue[0] = e;
        } else {
            siftUp(i, e);
        }

        return true;
    }

    private void siftUp(int k, E x) {
        siftUpComparable(k, x);
    }

    /**
     * 入队
     *
     * @param k
     * @param x
     */
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        log.info("【入队】元素：{} 当前队列：{}", JSON.toJSONString(key), JSON.toJSONString(queue));
        while (k > 0) {
            // 获取父节点Idx，相当于除以2
            int parent = (k - 1) >>> 1;
            log.info("【入队】寻找当前节点的父节点位置。k：{} parent：{}", k, parent);
            // 获取父节点元素
            Object parentValue = queue[parent];
            // 如果当前位置元素，大于父节点元素，则退出循环
            if (key.compareTo((E) parentValue) >= 0) {
                log.info("【入队】值比对，父节点：{} 目标节点：{}", JSON.toJSONString(parentValue), JSON.toJSONString(key));
                break;
            }
            // 相反父节点位置大于当前位置元素，则进行替换
            log.info("【入队】替换过程，父子节点位置替换，继续循环。父节点值：{} 存放到位置：{}", JSON.toJSONString(parentValue), k);
            queue[k] = parentValue;
            k = parent;
        }
        queue[k] = key;
        log.info("【入队】完成 Idx：{} Val：{} \r\n当前队列：{} \r\n", k, JSON.toJSONString(key), JSON.toJSONString(queue));
    }

    /**
     * 扩容的逻辑
     *
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + (oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1);

        // 可能会溢出
        if (newCapacity - (Integer.MAX_VALUE - 8) > 0) {
            newCapacity = (minCapacity > Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8;
        }

        queue = Arrays.copyOf(queue, newCapacity);
    }

    @Override
    public boolean add(E e) {
        return offer(e);
    }

    @Override
    public E poll() {
        return null;
    }

    @Override
    public E peek() {
        return null;
    }
}
